The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
Set constraints are relations between sets of terms. They have been used extensively in various applications in program analysis and type inference. We present several results on the computational complexity of solving systems of set constraints. The systems we study form a natural complexity hierarchy depending on the form of the constraint language.
We consider the modal μ-calculus due to Kozen, which is a finitary modal logic with least and greatest fixed points of monotone operators. We extend the existing duality between the category of modal algebras with homomorphisms and the category of descriptive modal frames with contractions to the case of having fixed point, operators. As a corollary, we obtain a completeness result for Kozen's original...
It is shown how the schema of equivalence can be used to obtain short proofs of tautologies A, where the depth of proofs is linear in the number of variables in A.
We introduce typed combinatory process algebra, a system combining process algebra with types and combinators. We describe its syntax and semantics, and by way of example, verify within this frame-work the Simple Alternating Bit Protocol.
Process algebras such as Milner's Calculus of Communicating Systems (CCS) are universalist, i.e., they assume that there is a single universe in which expressions are to be interpreted. We begin an investigation of a model theoretic approach to concurrency in which there are many universes. The classical result reconciling the universalist and model theoretic approaches in equational logic is the...
Backtracking searches for one solution only can easily be parallelized: Each processor searches a subtree of the search tree and all processors stop when one of them has found a solution. It has raised some interest that the average speedup observable may be ≩ the number of processors, a phenomenon which is called average superlinear speedup. As this observation does not seem to be provable for principal...
In this paper we extend recent work about logical criteria for approximation properties of optimization problems. We focus on the relationship between logical expressibility and expected asymptotic growth of optimal solutions on random inputs. This further develops a probabilistic approach due to Behrendt, Compton and Grädel showing that expected optimal solutions for any problem in the class Max...
In this paper we prove that for each k, the expressive power of k-ary fixed-point logic, i.e. the fragment of fixed-point logic whose fixed-point operators are restricted to arity ≤ k, strictly exceeds the power of (k − 1)-ary fixed-point logic. This solves a problem that was posed by Chandra and Harel in 1982. Our proof has a rather general form that applies to several variants of fixed-point...
We prove that trace equivalence is undecidable for the very small and natural subclass of Petri nets in which no transition requires more than one token; this subclass corresponds exactly to the calculus BPP of Christensen for which bisimulation equivalence is known to be decidable. We present this result along with a survey of decidability results for various notions of equivalence with respect to...
Set constraints are inclusion relations between sets of ground terms over a ranked alphabet. They have been used extensively in program analysis and type inference. Here we present an equational axiomatization of the algebra of set constraints. Models of these axioms are called termset algebras. They are related to the Boolean algebras with operators of Jónsson and Tarski. We also define a family...
We describe a general way of building logics with Lindström quantifiers, which capture regular complexity classes on ordered structures with polysize reductions. We then extend this method so as to accommodate complexity classes based on oracle Turing machines. Our main result shows an equivalence between enhancing a logic with a Lindström quantifier and enhancing a complexity class with an oracle...
In this paper we prove that there exists a Horn clauseHsuch that the problem: given a Horn clause G. Is G a consequence of H? is not recursive. Equivalently, there exists a one-clause PROLOG program such that there is no PROLOG implementation answering TRUE if the program implies a given goal and FALSE otherwise. We give a short survey of earlier results concerning clause implication and prove a classical Linial-Post theorem as a consequence of one of them...
Action calculi are a broad class of algebraic structures, including a formulation of Petri nets as well as a formulation of the π-calculus. Each action calculus HAC(K) is generated by a particular set K of operators called controls. The purpose of this paper is to extend action calculi in a uniform manner to higher-order. A special case is essentially the extension of the π-calculus to higher order...
Hyland and Ong [HO93] recently showed that given an arbitrary (right-absorptive) conditionally partial combinatory algebra (Cpca), there is a systematic way to construct a Kreisel-style modified realizability topos which has more than sufficient completeness properties to provide a categorical semantics for a wide range of higher type theories. Based on the topos generated from the C-pca of an appropriate...
This work presents an extension of system AF2 to allow the use of infinite data types. We extend the logic with inductive and coinductive types, and show that the “programming method” is still correct. We prove propositions about the normalization of typed terms. Moreover, since we only use the pure λ-calculus to represent data types, we prove uniqueness of the representation of data up...
A ”linear — style” sequent calculus makes it possible to explore the close structural relationships between primitive recursive programs and their inductive termination proofs, and between program transformations and their corresponding proof transformations. In this context the recursive — to — tail — recursive transformation corresponds proof theoretically to a certain kind of cut elimination, called here ”call by value cut elimination”...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.